package com.chj.zhongji.class05;

public class Code01_01_FibonacciProblem {

	public static int f1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		return f1(n - 1) + f1(n - 2);
	}

	public static int f2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
//		int res = 1;
//		int pre = 1;
//		int tmp = 0;
//		for (int i = 3; i <= n; i++) {
//			tmp = res;
//			res = res + pre;
//			pre = tmp;
//		}
//		return res;

		int pre1 = 1;
		int pre2 = 1;
		int ans = 0;
		for (int i = 3; i <= n; i++) {
			ans = pre1 + pre2;
			pre1 = pre2;
			pre2 = ans;
		}
		return ans;
	}

	public static int f3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		int[][] base = { { 1, 1 }, { 1, 0 } };
		int[][] res = matrixPower(base, n - 2);
		return res[0][0] + res[1][0];
	}

	public static int[][] matrixPower(int[][] m, int n) {
		int[][] res = new int[m.length][m[0].length];
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		int[][] tmp = m;
		for (int p = n; p != 0; p >>= 1) {
			if ((p & 1) != 0) {
				res = muliMatrix(res, tmp);
			}
			tmp = muliMatrix(tmp, tmp);
		}
		return res;
	}

	public static int[][] muliMatrix(int[][] m1, int[][] m2) {
		int[][] res = new int[m1.length][m2[0].length];
		for (int i = 0; i < m1.length; i++) {
			for (int j = 0; j < m2[0].length; j++) {
				for (int k = 0; k < m2.length; k++) {
					res[i][j] += m1[i][k] * m2[k][j];
				}
			}
		}
		return res;
	}

	public static int s1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		return s1(n - 1) + s1(n - 2);
	}

	public static int s2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		int res = 2;
		int pre = 1;
		int tmp = 0;
		for (int i = 3; i <= n; i++) {
			tmp = res;
			res = res + pre;
			pre = tmp;
		}
		return res;
	}

	public static int s3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		int[][] base = { { 1, 1 }, { 1, 0 } };
		int[][] res = matrixPower(base, n - 2);
//		return 2 * res[0][0] + res[1][0];
		return 2 * res[0][0] + res[1][0];
	}

	public static int c1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}
		return c1(n - 1) + c1(n - 3);
	}

	public static int c2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}

		int[] dp = new int[4];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		int res = 0;
		for (int i = 4; i < n + 1; i++) {
			res = dp[1] + dp[3];
			dp[1] = dp[2];
			dp[2] = dp[3];
			dp[3] = res;
		}

		return res;

//		int[] dp = new int[n + 1];
//		dp[1] = 1;
//		dp[2] = 2;
//		dp[3] = 3;
//		for (int i = 4; i < dp.length; i++) {
//			dp[i] = dp[i - 1] + dp[i - 3];
//		}

//		return dp[n];
//		int res = 3;
//		int pre = 2;
//		int prepre = 1;
//		int tmp1 = 0;
//		int tmp2 = 0;
//		for (int i = 4; i <= n; i++) {
//			tmp1 = res;
//			tmp2 = pre;
//			res = res + prepre;
//			pre = tmp1;
//			prepre = tmp2;
//		}
//		return res;
	}

	public static int c3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}
		int[][] base = { { 1, 1, 0 }, { 0, 0, 1 }, { 1, 0, 0 } };
		int[][] res = matrixPower(base, n - 3);
		return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
	}

	// 定义三个变量方法
	public static void demo1() {
		int a = 1, b = 1, c = 0;
		System.out.println("斐波那契数列前20项为：");
		System.out.print(a + "\t" + b + "\t");
		// 因为前面还有两个1、1 所以i<=18
		for (int i = 1; i <= 18; i++) {
			c = a + b;
			a = b;
			b = c;
			System.out.print(c + "\t");
			if ((i + 2) % 5 == 0)
				System.out.println();
		}
	}

	// 定义数组方法
	public static void demo2() {
		int arr[] = new int[20];
		arr[0] = arr[1] = 1;
		for (int i = 2; i < arr.length; i++) {
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		System.out.print("斐波那契数列的前20项如下所示：");
		for (int i = 0; i < arr.length; i++) {
			if (i % 5 == 0)
				System.out.println();
			System.out.print(arr[i] + "\t");
		}
	}

	// 使用递归方法
	private static int getFibo(int i) {
		if (i == 1 || i == 2)
			return 1;
		else
			return getFibo(i - 1) + getFibo(i - 2);
	}

	public static void demo3() {
//		// 使用递归方法
//		private static int getFibo(int i) {
//			if (i == 1 || i == 2)
//				return 1;
//			else
//				return getFibo(i - 1) + getFibo(i - 2);
//		}

		System.out.println("斐波那契数列的前20项为：");
		for (int j = 1; j <= 20; j++) {
			System.out.print(getFibo(j) + "\t");
			if (j % 5 == 0)
				System.out.println();
		}
	}

	public static void main(String[] args) {
		int n = 7;
		System.out.println(f1(n));
		System.out.println(f2(n));
		System.out.println(f3(n));
		System.out.println("===");

		System.out.println(s1(n));
		System.out.println(s2(n));
		System.out.println(s3(n));
		System.out.println("=ccc==");

		System.out.println(c1(n));
		System.out.println(c2(1964456565));
		System.out.println(c3(1964456565));
		System.out.println("=ccc==");
		System.out.println("===");
		demo1();
		demo2();
		System.out.println();
		demo3();
		System.out.println("===");
		int p = 75;
		System.out.println((p & 1));
		int q = 4;
		System.out.println((q & 1));
		System.out.println((6 & 3));
		for (; p != 0; p >>= 1) {
			if ((p & 1) != 0) {
				System.out.println("&1: " + p);
			}
			System.out.println(">>= 1: " + p);
		}

		for (int i = 0; i != 20; i++) {
			System.out.println(c1(i));
		}
	}

}
